#include <cstdlib>
#include <vector>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
private:
    void dfs(TreeNode* node, int sum, vector<int>& store, vector<vector<int>>& ans) {
        if (node == nullptr) {
            return;
        }
        sum -= node->val;
        store.emplace_back(node->val);
        if (sum == 0 && node->left == nullptr && node->right == nullptr) {
            ans.emplace_back(store);
            store.pop_back();
            return;
        }
        dfs(node->left, sum, store, ans);
        dfs(node->right, sum, store, ans);
        store.pop_back();
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> ans;
        vector<int> store;
        dfs(root, sum, store, ans);
        return ans;
    }
};